/**
*      author: Y_Yao
*      created: 2024-09-27 22:32:56
**/

#include<bits/stdc++.h>
#include<unordered_map>

using namespace std;
using LL = long long;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 9;
int v[N],w[N];
int n,m;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for(int i = 0;i < n;i++) cin >> v[i] >> w[i];

    vector<vector<int>> dp(m+1,vector<int>(16+9,-INF));
    dp[0][0] = 0;
    for(int i = 1;i <= m;i++)
    {
        for(int j = 0;j < 16;j++)
        {
            for(int k = 0;k < n;k++)
            {
                if(i >= v[k] && j >= w[k] % 16)
                {
                    dp[i][j] = max(dp[i-v[k]][(j-w[k]%16)%16] + 1,dp[i][j]);
                }
            }
        }
    }

    for(int i = 1;i <= m;i++)
    {
        for(int j = 0;j < 16;j++)
        {
            cout <<dp[i][j] <<" ";
        }
        cout << endl;
    }
 
    int ret = -INF;
    for(int i = 0;i <= m;i++) ret = max(ret,dp[i][0]);
    cout << ret << endl;
    return 0;
}